/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-14
 * Time: 21:24
 */
public class Solution {
    public static int numDistinct (String S, String T) {
        int row = S.length();
        int col = T.length();
        // F(i, j) 表示 S 的前 i 个字符中能找出来的 T 的子串的数目
        int[][] numD = new int[row+1][col+1];
        // 每个字符串都能找出来一个空串, 可以根据递推方程看出, 第一列必须为 1
        for (int i = 0; i <= row; i++) {
            numD[i][0] = 1;
        }
        for (int i = 1; i <= row ; i++) {
            for (int j = 1; j <= col ; j++) {
                // 如果 s[i] == t[j] 那么, 就可以考虑使用不使用 s[i] 这个字符
                // 用则 是 F(i-1, j-1)
                // 不用则是 F(i, j-1)
                // 所以总共的是 F(i-1, j-1) + F(i-1, j)
                if(S.charAt(i-1) == T.charAt(j-1)){
                    numD[i][j] = numD[i-1][j-1] + numD[i-1][j];
                }else{
                    // s[i] != t[j]
                    // 那么退化为 F(i-1, j)
                    numD[i][j] = numD[i-1][j];
                }
            }
        }
        return numD[row][col];
    }


    /**
     * 空间优化, 使用滚动数组
     * @param S
     * @param T
     * @return
     */
    public static int numDistinct2 (String S, String T) {
        int row = S.length();
        int col = T.length();
        // F(i, j) 表示 S 的前 i 个字符中能找出来的 T 的子串的数目
        int[] numD = new int[col+1];
        // 每个字符串都能找出来一个空串, 可以根据递推方程看出, 第一列必须为 1
        for (int i = 0; i <= row; i++) {
            numD[0] = 1;
        }
        for (int i = 1; i <= row ; i++) {
            // 注意一维的话, 因为需要用到前面列的信息
            // 所以要从后往前更新
            for (int j = col; j > 0 ; j--) {
                // 如果 s[i] == t[j] 那么, 就可以考虑使用不使用 s[i] 这个字符
                // 用则 是 F(i-1, j-1)
                // 不用则是 F(i, j-1)
                // 所以总共的是 F(i-1, j-1) + F(i-1, j)
                if(S.charAt(i-1) == T.charAt(j-1)){
                    numD[j] = numD[j-1] + numD[j];
                }
                // 一维的话 s[i] != t[j]
                // 结果退化 为 F(i-1, j)
                // 不就用更新了
            }
        }
        return numD[col];
    }
}
